主存|局部性_交易系统开发技能及面试之低延迟编程技术

篇首语：本文由编程笔记#小编为大家整理，主要介绍了交易系统开发技能及面试之低延迟编程技术相关的知识，希望对你有一定的参考价值。

文章目录

• 概要
• CPU Caches
• • Q1 分析代码段性能
  • Q2 采用alignas进行性能优化
  • Q3 缩小锁粒度
  
  
• kernel bypass
• 非阻塞编程
• 编程技巧
• 编译优化
• Q4 分析性能
• 漫谈

关于低延迟相关技术&＃xff0c;需要我们掌握cpu cache工作原理、kernel bypass、非阻塞编程、编译优化、硬件优化&＃xff08; CPU pipelines&＃xff0c;FPGA&＃xff09;、软件优化&＃xff08;高效算法和数据结构&＃xff09;

Cacheline(缓存行)&＃xff1a;内存与缓存的交互总是以cachelline大小进行拷贝。比如&＃xff1a;cpu传输一个整型变量时&＃xff08;4或8字节&＃xff09;&＃xff0c;采用的是一个cacheline大小&＃xff08;主流cpu是64字节&＃xff09;进行传输&＃xff0c;可以理解cacheline为最小缓存单位。

缓存的类型&＃xff1a;指令缓存&＃xff08;程序指令&＃xff09;&＃xff0c;数据缓存&＃xff08;程序数据&＃xff09;&＃xff0c;虚拟内存与物理内存的映射缓存。

缓存等级&＃xff1a;cpu寄存器 -> L1缓存 -> L2 缓存 -> L3缓存 -> 主存&＃xff0c; 越靠近cpu寄存器的位置速度越快。

缓存一致性&＃xff1a;对在不同的缓存和主存之间的数据一致性处理。

时间局部性 Temporal Locality&＃xff1a;指最近使用的数据更有可能再被使用。

空间局部性 Spatial Locality&＃xff1a;如果内存中某个位置的数据正在被cpu所使用&＃xff0c;那么靠近这个内存位置的内存数据很可能在不久的将来被引用。

缓存预热 &＃xff1a;当数据第一次被cpu引用时&＃xff0c;数据被从主存放置到缓存中。缓存预热是为了增加缓存命中&＃xff0c;而预测即将使用的数据并把其加载到缓存中。

**CPU 绑定&＃xff0c;pinning **&＃xff1a; 指将进程和某个或者某几个 CPU 关联绑定&＃xff0c;绑定后的进程只能在所关联的 CPU 上运行&＃xff0c;可提高缓存命中率。

Q1 分析代码段性能

分别采用行、列访问数据的方式&＃xff1a;

// row major order
std::vector<double> v(n * n);
double sum0.0;
for (std::size_t i &＃61; 0; i < n; i&＃43;&＃43;)
for (std::size_t j &＃61; 0; j < n ; j&＃43;&＃43;)
sum &＃43;&＃61; v[i * n &＃43; j];


// column major order
std::vector<double> v(n * n);
double sum0.0;
for (std::size_t j &＃61; 0; j < n; j&＃43;&＃43;)
for (std::size_t i &＃61; 0; i < n ; i&＃43;&＃43;)
sum &＃43;&＃61; v[i * n &＃43; j];




根据空间局部性和Cacheline&＃xff0c;采用行式访问数据性能更好&＃xff0c;因为cpu读取数据时采用cacheline大小将内存空间上线性数据加载到缓存中。即采用行方式遍历数据时&＃xff0c;下一个数据已在Cache中&＃xff0c;提高了Cache的命中率。

Q2 采用alignas进行性能优化

观察以下代码&＃xff1a;

struct Data
char c;
char d;
;
Data data;
void thread1_func()
int sum &＃61; 0;
for (int i &＃61; 0; i < 100000000; &＃43;&＃43;i)
sum &＃43;&＃61; data.c;


void thread2_func()
int sum &＃61; 0;
for (int i &＃61; 0; i < 100000000; &＃43;&＃43;i)
data.d &＃61; i % 256;




采用两个线程并发执行以上两个函数&＃xff0c;因为Data结构的c\\d都是1个字节&＃xff0c;而cacheline普遍为64个字节&＃xff0c;所以当执行data.d的更新时&＃xff0c;cpu会采用cacheline大小更新缓存到主存的数据&＃xff0c;导致data.c无法命中缓存。因为data.d需要更新&＃xff0c;那么我们可以设置缓存只更新data.d大小&＃xff08;1个字节&＃xff09;&＃xff0c;所以可以使用alignas制定内存对齐大小。

struct alignas(1) Data
char c;
char d;
;


Q3 缩小锁粒度

long long sum &＃61; 0;
void sumUp()
long long tmp &＃61; 0;
for (int i &＃61; 0; i < 10000; &＃43;&＃43;i)
tmp &＃43;&＃61; 1;

std::lock_guard<std::mutex> lockGuard(myMutex);
sum &＃43;&＃61; tmp;



当有多个线程对全局变量sum进行操作时&＃xff0c;可以在对sum进行操作时才进行锁&＃xff0c;而sum的累计先采用本地变量tmp进行计算后才更新sum变量。

Kernel bypass是一种绕过OS与网络栈或者其他硬件进行数据交互的技术&＃xff0c;通过减少用户态与内核态的数据拷贝&＃xff08;也叫零拷贝zero-copy&＃xff09;来提升性能。

通常将的NIO方式&＃xff0c;比如sockets 或者 设计一套异步事件响应系统&＃xff0c;在生产中常用Actor模型。
这一块的知识在前篇系列文章都有讲到过。

1、 避免动态内存分配
采用内存池&＃xff08;对象池&＃xff09;&＃xff0c;减少内存的分配释放以及内存碎片的产生。

2、 采用位运算替换数值运算
比如 n/2 可以采用 n >> 1的方式性能更高。

3、利用cacheline&＃xff0c;让即将使用到的数据更紧凑的在同一个cacheline大小范围内&＃xff0c;提高cache命中率。

4、交易系统场景里需要使用到浮点数值来表示数据&＃xff0c;比如股票价格10.01&＃xff0c;而优化的方式是使用整型&＃xff1a;1010&＃xff08;price&＃xff09;&＃xff0c;小数点位为 2&＃xff08;factor&＃xff09;这种形式。

5、因为cacheline预加载cache&＃xff0c;当数据量少时&＃xff0c;采用线性查找比二分查找性能更好

6、

采用__builtin_expect做分支预测。它是gcc编译器引入的一个指令&＃xff0c;允许程序员将代码中最有可能执行的分支告诉编译器。具体的写法

__builtin_expect(EXP,N) // 其中EXP可以为变量&＃xff0c;也可以为表达式


意思是&＃xff0c;EXP&＃61;&＃61;n的概率很大。

//预测x更大几率为false
if (__builtin_expect(x, 0))
foo();
...

else
bar();
...



以上代码生成汇编&＃xff1a;

cmp $x,0
jne _foo
_bar:
call bar
...
jmp after_if
_foo:
call foo
...
after_if:


简化版的cpu流水线&＃xff08;cpu pipeline&＃xff09;

分支预测器位于整个CPU核心流水线的差不多最前端部分&＃xff0c;靠近IF的级。从指令缓存里面读取指令时&＃xff0c;需要由分支预测器来判断从哪里读取。
所以采用分支预测实际上是优化了分支预测期的缓存。

随机初始化数组值&＃xff0c;然后统计随机数中大于等于128的值

const unsigned arraySize &＃61; 32768;
int data[arraySize];
for (unsigned c &＃61; 0; c < arraySize; &＃43;&＃43;c)
data[c] &＃61; std::rand() % 256;


clock_t start &＃61; clock();
long long sum &＃61; 0;
for (unsigned i &＃61; 0; i < 100000; &＃43;&＃43;i)
//primary loop
for (unsigned c &＃61; 0; c < arraySize; &＃43;&＃43;c)
if (data[c] >&＃61; 128)
sum &＃43;&＃61; data[c];



double elapsedTime &＃61; static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
std::cout << elapsedTime << endl;//17.979


初始化完数值后&＃xff0c;先进行排序&＃xff0c;再统计大于等于128的值

const unsigned arraySize &＃61; 32768;
int data[arraySize];
for (unsigned c &＃61; 0; c < arraySize; &＃43;&＃43;c)
data[c] &＃61; std::rand() % 256;

//先进行排序
std::sort(data, data &＃43; arraySize);

clock_t start &＃61; clock();
long long sum &＃61; 0;
for (unsigned i &＃61; 0; i < 100000; &＃43;&＃43;i)
//primary loop
for (unsigned c &＃61; 0; c < arraySize; &＃43;&＃43;c)
if (data[c] >&＃61; 128)
sum &＃43;&＃61; data[c];



double elapsedTime &＃61; static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
std::cout << elapsedTime << endl; //5.909


排序后的执行性能提升了至少3倍&＃xff0c;而且你使用vscode2019的诊断工具时&＃xff0c;可以看到cpu有个跃式的进度跳动。
排序后的性能高是因为现代cpu都采用了长流水线工作方式&＃xff0c;也即是前文讲到的cpu pipeline&＃xff0c;在执行指令时会采用分支预测方式&＃xff0c;在统计数值时:

if (data[c] >&＃61; 128)
sum &＃43;&＃61; data[c];



而如果没有排序的话&＃xff0c;分支预测的错误性更高且随机&＃xff0c;那么指令缓存毫无意义&＃xff0c;排序后使分支预测为常态。

如果是高频交易系统的话&＃xff0c;最好采用集中式服务&＃xff0c;比如让数据、计算都在一个进程&＃xff0c;让数据跟计算更紧凑&＃xff0c;而不是采用当前的互联网微服务开发思维。

还有就是当前越来越重要的FPGA矩阵编程&＃xff0c;可以饶过CPU在FPGA上进行市场数据分析